package com.bo.day20231222;


/**
 * 递归方式实现
 * 二叉树
 * 先序：头,左,右
 * 中序：左,头,右
 * 后序：左,右,头
 * 图解：https://cloud.fynote.com/share/d/XHKVV8I7
 * @Author: gpb
 * @Date: 2023/12/22 16:52
 * @Description:
 */
public class RecursiveTraversalBT {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node (int v) {
            value = v;
        }
    }

    /**
     * 先序：头,左,右
     *
     * @param head
     */
    public static void pre (Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.value + " ");
        pre(head.left);
        pre(head.right);
    }

    /**
     * 中序：左、头、右
     *
     * @param head
     */
    public static void in (Node head) {
        if (head == null) {
            return;
        }
        in(head.left);
        System.out.print(head.value + " ");
        in(head.right);
    }

    /**
     * 后序：左,右,头
     *
     * @param head
     */
    public static void pos (Node head) {
        if (head == null) {
            return;
        }
        pos(head.left);
        pos(head.right);
        System.out.print(head.value + " ");
    }

    public static void f (Node head) {
        if (head == null) {
            return;
        }
        // 1 先序
        f(head.left);
        // 2 中序
        f(head.right);
        // 3 后序
    }

    public static void main (String[] args) {
        Node node = new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.right = new Node(5);
        node.right.left = new Node(6);
        node.right.right = new Node(7);
        // 1,2,4,5,3,6,7
        System.out.println("======先序=====");
        pre(node);
        System.out.println("===============");
        // 4,2,5,1,6,3,7
        System.out.println("======中序=====");
        in(node);
        System.out.println("===============");
        // 4,5,2,6,7,3,1
        System.out.println("======后序=====");
        pos(node);
        System.out.println("===============");
    }

}
